package dp.一维数组;

import java.util.Arrays;

/**
 * https://leetcode.cn/problems/house-robber/?favorite=2cktkvj
 *
 * 题解：https://mp.weixin.qq.com/s/z44hk0MW14_mAQd7988mfw
 */
public class _198_打家劫舍 {

    public static void main(String[] args) {
        int[] nums = new int[]{1,2,3,1};
        _198_打家劫舍 _198_打家劫舍 = new _198_打家劫舍();
        int result = _198_打家劫舍.rob(nums);
        System.out.println(result);
    }

    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];
        meno = new int[nums.length];
        Arrays.fill(meno,-1);
        return dp(nums, 0);
    }


    int[] meno;

    private int dp(int[] nums, int start) {
        if (start >= nums.length) return 0;

        if (meno[start] != -1) {
            return meno[start];
        }

        meno[start] = Math.max(
                // 不抢，去下家
                dp(nums, start + 1),
                // 抢，顺便抢下下家
                nums[start] + dp(nums, start + 2));

        return meno[start];
    }
}
